//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
//
// 
//
// 示例: 
//
// 输入："23"
//输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
// 
//
// 说明: 
//尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 
// Related Topics 深度优先搜索 递归 字符串 回溯算法 
// 👍 1079 👎 0


import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    String[] numbers={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.equals(""))//需要特判一下传入的字符数组是否为空 若为空 则直接返回结果[]  若没有特判 则结果为[""]
            return  result;
        dfs(digits,0,"");
        return result;
    }
    private void  dfs(String digits, int index,String s){
        if(digits.length()==index)
        {
            result.add(s);
            return;//java 语法必须要添加返回语句 否则会产生异常
        }
        Character c=digits.charAt(index);
        String cString=numbers[c-'0'];
        for (int i = 0; i < cString.length(); i++) {//遍历下一个数字的字母
            dfs(digits,index+1,s+cString.charAt(i));
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
